import java.util.ArrayList;
import java.util.List;

public class FindAnagrams {
    public List<Integer> findAnagrams(String s, String p) {
        // hash1用于记录p字符串中字符出现的次数
        int[] hash1 = new int[26];
        // hash2用于记录窗口中字符出现的次数
        int[] hash2 = new int[26];
        for (char c : p.toCharArray()) {
            hash1[c-'a']++;
        }
        char[] c = s.toCharArray();
        List<Integer> ret = new ArrayList<>();
        // count记录窗口中有效字符的个数
        int count = 0;
        for (int left = 0, right = 0; right < c.length; right++) {
            if (++hash2[c[right]-'a'] <= hash1[c[right]-'a']) {
                count++;
            }
            if (right - left >= p.length()) {
                if (hash2[c[left]-'a']-- <= hash1[c[left++]-'a']) {
                    count--;
                }
            }
            if (count == p.length()) ret.add(left);
        }
        return ret;
    }

    public static void main(String[] args) {
        String s = "cbaebabacd";
        String p = "abc";
        List<Integer> ret = new FindAnagrams().findAnagrams(s, p);
        System.out.println(ret);
    }
}
